#include <assert.h>
#include <iostream>
using namespace std;

template <class T>
struct list_node
{ // 使用struct公开成员变量，方便Mylist直接进行访问。
  T _data;
  list_node *_next;
  list_node *_prev;

  list_node(const T &)
      : _data(val),
        _next(nullptr),
        _prev(nullptr)
  {
  }

  list_node(T &&val = T())
      : _data(forward<T>(val)),
        _next(nullptr),
        _prev(nullptr)
  {
  }
};

// list_iterator的成员变量只有一个指向节点的指针。
// 但其中封装了list迭代器的方法：
// 1.解引用返回数据_data引用
// 2.箭头返回数据_data的地址
// 3.++操作实现了链表指针的移动
template <class T, class Ref, class Ptr>
struct list_iterator
{
  typedef list_node<T> Node;
  typedef list_iterator<T, Ref, Ptr> iterator;
  Node *_pnode;

  list_iterator(Node *pnode)
      : _pnode(pnode)
  {
  }

  // list_iterator的拷贝构造，析构，赋值重载使用默认生成的即可。

  //*和->操作涉及普通对象和const对象的权限问题，需要传入Ref和Ptr泛型返回值，
  // 普通对象传普通引用和普通指针；const对象传const引用和const指针。
  // 这里还要区分const list对象和const iterator对象。
  Ref operator*() const
  {
    return _pnode->_data;
  }

  Ptr operator->() const
  {
    return &(_pnode->_data);
  }

  iterator &operator++()
  {
    _pnode = _pnode->_next;
    return *this;
  }

  iterator operator++(int)
  {
    iterator tmp(*this);
    _pnode = _pnode->_next;
    return tmp;
  }

  iterator &operator--()
  {
    _pnode = _pnode->_prev;
    return *this;
  }

  iterator operator--(int)
  {
    iterator tmp(*this);
    _pnode = _pnode->_prev;
    return tmp;
  }

  bool operator!=(const iterator &it) const
  {
    return _pnode != it._pnode;
  }

  bool operator==(const iterator &it) const
  {
    return _pnode == it._pnode;
  }
};

template <class T>
class Mylist
{
  typedef list_node<T> Node;
  Node *_phead;

public:
  typedef list_iterator<T, T &, T *> iterator;
  typedef list_iterator<T, const T &, const T *> const_iterator;
  // constructor & destructor
  Mylist()
  {
    empty_initialize();
  }

  Mylist(const Mylist &mlt)
  {
    empty_initialize(); // 交换前必须要进行空初始化，否则会访问野指针崩溃
    Mylist tmp(mlt.begin(), mlt.end());
    swap(tmp);
  }

  Mylist(Mylist &&mlt)
  {
    empty_initialize();
    swap(mlt);
  }

  Mylist &operator=(const Mylist &mlt)
  {
    Mylist tmp(mlt.begin(), mlt.end());
    swap(tmp);
    return *this;
  }

  Mylist &operator=(Mylist &&mlt)
  {
    swap(mlt);
    return *this;
  }

  void empty_initialize()
  {
    _phead = new Node(T());
    _phead->_next = _phead;
    _phead->_prev = _phead;
  }

  template <typename InputIterator>
  Mylist(InputIterator first, InputIterator last)
  {
    empty_initialize(); // 交换前必须要进行空初始化，否则会访问野指针崩溃
    while (first != last)
    {
      push_back(*first);
      ++first;
    }
  }

  void swap(Mylist &mlt)
  {
    std::swap(_phead, mlt._phead);
  }

  iterator insert(iterator pos, const T &val)
  {
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *newnode = new Node(val);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);
  }

  iterator insert(iterator pos, T &&val)
  {
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *newnode = new Node(forward<T>(val));
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    return iterator(newnode);
  }

  void push_back(const T &val)
  {
    insert(end(), val);
  }

  void push_back(T &&val)
  {
    insert(end(), forward<T>(val));
  }

  void push_front(const T &val)
  {
    insert(begin(), val);
  }

  void push_front(T &&val)
  {
    insert(begin(), forward<T>(val));
  }

  iterator erase(iterator pos)
  {
    assert(pos != end());
    Node *cur = pos._pnode;
    Node *prev = cur->_prev;
    Node *next = cur->_next;
    next->_prev = prev;
    prev->_next = next;
    delete cur;
    return iterator(next);
  }

  void pop_back()
  {
    assert(_phead->_next != _phead);
    erase(--end());
  }

  void pop_front()
  {
    assert(_phead->_next != _phead);
    erase(begin());
  }

  void clear()
  {
    iterator it = begin();
    while (it != end())
    {
      it = erase(it);
    }
  }

  ~Mylist()
  {
    clear();       // 清除所有数据节点
    delete _phead; // 释放哨兵位节点
  }

  // iterator
  iterator begin()
  {
    return iterator(_phead->_next);
  }

  iterator end()
  {
    return iterator(_phead);
  }

  const_iterator begin() const
  {
    return const_iterator(_phead->_next);
  }

  const_iterator end() const
  {
    return const_iterator(_phead);
  }
};
